home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DDJMAG / DDJ9006.ZIP / REGAN.LST < prev    next >
File List  |  1990-05-02  |  11KB  |  314 lines
  1. _LZW REVISITED_
  2. by Shawn M. Regan
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. /* Basic LZW Data Compression program published in DDJ October 1989 issue.
  8.  * Original Author: Mark R. Nelson
  9.  * Updated by: Shawn M. Regan, January 1990
  10.  * Added: - Method to clear table when compression ratio degrades
  11.  *        - Self adjusting code size capability (up to 14 bits)
  12.  * Updated functions are marked with "MODIFIED". main() has been updated also
  13.  * Compile with -ml (large model) for MAX_BITS == 14 only
  14.  */
  15.  
  16. #include <stdio.h>
  17.  
  18. #define INIT_BITS 9
  19. #define MAX_BITS 14           /* Do not exceed 14 with this program */
  20. #define HASHING_SHIFT MAX_BITS - 8
  21.  
  22. #if MAX_BITS == 14            /* Set the table size. Must be a prime    */
  23. #define TABLE_SIZE 18041      /* number somewhat larger than 2^MAX_BITS.*/
  24. #elif MAX_BITS == 13
  25. #define TABLE_SIZE 9029
  26. #else
  27. #define TABLE_SIZE 5021
  28. #endif
  29.  
  30. #define CLEAR_TABLE 256    /* Code to flush the string table */
  31. #define TERMINATOR  257    /* To mark EOF Condition, instead of MAX_VALUE */
  32. #define FIRST_CODE  258    /* First available code for code_value table */
  33. #define CHECK_TIME  100    /* Check comp ratio every CHECK_TIME chars input */
  34.  
  35. #define MAXVAL(n) (( 1 <<( n )) -1)   /* max_value formula macro */
  36.  
  37. unsigned input_code();
  38. void *malloc();
  39.  
  40. int *code_value;                      /* This is the code value array */
  41. unsigned int *prefix_code;            /* This array holds the prefix codes */
  42. unsigned char *append_character;      /* This array holds the appended chars */
  43. unsigned char decode_stack[4000];     /* This array holds the decoded string */
  44.  
  45. int num_bits=INIT_BITS;               /* Starting with 9 bit codes */
  46. unsigned long bytes_in=0,bytes_out=0; /* Used to monitor compression ratio */
  47. int max_code;                         /* old MAX_CODE */
  48. unsigned long checkpoint=CHECK_TIME;  /* For compression ratio monitoring */
  49.  
  50. main(int argc, char *argv[])
  51. {
  52.    FILE *input_file, *output_file, *lzw_file;
  53.    char input_file_name[81];
  54.  /* The three buffers for the compression phase.  */
  55.    code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
  56.    prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
  57.    append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
  58.  
  59.    if (code_value==NULL || prefix_code==NULL || append_character==NULL) {
  60.       printf("Error allocating table space!\n");
  61.       exit(1);
  62.    }
  63.  /* Get the file name, open it, and open the LZW output file. */
  64.    if (argc>1)
  65.       strcpy(input_file_name,argv[1]);
  66.    else {
  67.       printf("Input file name: ");
  68.       scanf("%s",input_file_name);
  69.    }
  70.    input_file=fopen(input_file_name,"rb");
  71.    lzw_file=fopen("test.lzw","wb");
  72.    if (input_file == NULL || lzw_file == NULL) {
  73.       printf("Error opening files\n");
  74.       exit(1);
  75.    }
  76.    max_code = MAXVAL(num_bits);     /* Initialize max_value & max_code */
  77.    compress(input_file,lzw_file);       /* Call compression routine */
  78.  
  79.    fclose(input_file);
  80.    fclose(lzw_file);
  81.    free(code_value);                    /* Needed only for compression */
  82.  
  83.    lzw_file=fopen("test.lzw","rb");
  84.    output_file=fopen("test.out","wb");
  85.    if (lzw_file == NULL || output_file == NULL) {
  86.       printf("Error opening files\n");
  87.       exit(1);
  88.    }
  89.    num_bits=INIT_BITS;                  /* Re-initialize for expansion */
  90.    max_code = MAXVAL(num_bits);
  91.    expand(lzw_file,output_file);        /* Call expansion routine */
  92.  
  93.    fclose(lzw_file);                    /* Clean it all up */
  94.    fclose(output_file);
  95.    free(prefix_code);
  96.    free(append_character);
  97. }
  98. /* MODIFIED This is the new compression routine. The first two 9-bit codes 
  99.  * have been reserved for communication between the compressor and expander.
  100.  */
  101. compress(FILE *input, FILE *output)
  102. {
  103.    unsigned int next_code=FIRST_CODE;
  104.    unsigned int character;
  105.    unsigned int string_code;
  106.    unsigned int index;
  107.    int i,             /* All purpose integer */
  108.    ratio_new,         /* New compression ratio as a percentage */
  109.    ratio_old=100;     /* Original ratio at 100% */
  110.  
  111.    for (i=0;i<TABLE_SIZE;i++)   /* Initialize the string table first */
  112.       code_value[i]=-1;
  113.    printf("Compressing\n");
  114.    string_code=getc(input);     /* Get the first code */
  115.  
  116.  /* This is the main compression loop. Notice when the table is full we try
  117.   * to increment the code size. Only when num_bits == MAX_BITS and the code
  118.   * value table is full do we start to monitor the compression ratio.
  119.   */
  120.    while((character=getc(input)) != (unsigned)EOF) {
  121.       if (!(++bytes_in % 1000)) {     /* Count input bytes and pacifier */
  122.          putchar('.');
  123.       }
  124.       index=find_match(string_code,character);
  125.       if (code_value[index] != -1)
  126.          string_code=code_value[index];
  127.       else {
  128.          if (next_code <= max_code ) {
  129.             code_value[index]=next_code++;
  130.             prefix_code[index]=string_code;
  131.             append_character[index]=character;
  132.          }
  133.          output_code(output,string_code);   /* Send out current code */
  134.          string_code=character;
  135.          if (next_code > max_code) {      /* Is table Full? */
  136.             if ( num_bits < MAX_BITS) {     /* Any more bits? */
  137.                putchar('+');
  138.                max_code = MAXVAL(++num_bits);  /* Increment code size then */
  139.             }
  140.             else if (bytes_in > checkpoint) {         /* At checkpoint? */
  141.                if (num_bits == MAX_BITS ) {
  142.                 ratio_new = bytes_out*100/bytes_in; /* New compression ratio */
  143.                 if (ratio_new > ratio_old) {        /* Has ratio degraded? */
  144.                   output_code(output,CLEAR_TABLE); /* YES,flush string table */
  145.                   putchar('C');
  146.                   num_bits=INIT_BITS;
  147.                   next_code=FIRST_CODE;        /* Reset to FIRST_CODE */
  148.                   max_code = MAXVAL(num_bits); /* Re-Initialize this stuff */
  149.                   bytes_in = bytes_out = 0;
  150.                   ratio_old=100;               /* Reset compression ratio */
  151.                   for (i=0;i<TABLE_SIZE;i++)   /* Reset code value array */
  152.                         code_value[i]=-1;
  153.                }
  154.                else                                /* NO, then save new */
  155.                ratio_old = ratio_new;            /* compression ratio */
  156.             }
  157.             checkpoint = bytes_in + CHECK_TIME;    /* Set new checkpoint */
  158.             }
  159.          }
  160.       }
  161.    }
  162.    output_code(output,string_code);   /* Output the last code */
  163.    if (next_code == max_code) {       /* Handles special case for bit */
  164.       ++num_bits;                     /* increment on EOF */
  165.       putchar('+');
  166.    }
  167.    output_code(output,TERMINATOR);    /* Output the end of buffer code */
  168.    output_code(output,0);             /* Flush the output buffer */
  169.    output_code(output,0);
  170.    output_code(output,0);
  171.    putchar('\n');
  172. }
  173. /* UNCHANGED from original
  174.  * This is the hashing routine.
  175.  */
  176. find_match(int hash_prefix, unsigned int hash_character)
  177. {
  178.    int index, offset;
  179.  
  180.    index = (hash_character << HASHING_SHIFT ) ^ hash_prefix;
  181.    if (index == 0 )
  182.       offset=1;
  183.    else
  184.       offset = TABLE_SIZE - index;
  185.    while(1) {
  186.       if (code_value[index] == -1 )
  187.          return(index);
  188.       if (prefix_code[index] == hash_prefix && 
  189.                                      append_character[index] == hash_character)
  190.          return(index);
  191.       index -= offset;
  192.       if (index < 0)
  193.          index += TABLE_SIZE;
  194.    }
  195. }
  196. /* MODIFIED This is the modified expansion routine. It must now check for the
  197.  * CLEAR_TABLE code and know when to increment the code size.
  198.  */
  199. expand(FILE *input, FILE *output)
  200. {
  201.    unsigned int next_code=FIRST_CODE;
  202.    unsigned int new_code;
  203.    unsigned int old_code;
  204.    int character,
  205.    counter=0,
  206.    clear_flag=1;          /* Need to clear the code value array */
  207.    unsigned char *string;
  208.    char *decode_string(unsigned char *buffer, unsigned int code);
  209.  
  210.    printf("Expanding\n");
  211.  
  212.    while((new_code=input_code(input)) != TERMINATOR) {
  213.       if (clear_flag) {       /* Initialize or Re-Initialize */
  214.          clear_flag=0;
  215.          old_code=new_code;   /* The next three lines have been moved */
  216.          character=old_code;  /* from the original */
  217.          putc(old_code,output);
  218.          continue;
  219.       }
  220.       if (new_code == CLEAR_TABLE) {     /* Clear string table */
  221.          clear_flag=1;
  222.          num_bits=INIT_BITS;
  223.          next_code=FIRST_CODE;
  224.          putchar('C');
  225.          max_code = MAXVAL(num_bits);
  226.          continue;
  227.       }
  228.       if (++counter == 1000) {           /* Pacifier */
  229.          counter=0;
  230.          putchar('.');
  231.       }
  232.       if (new_code >= next_code) {       /* Check for string+char+string */
  233.          *decode_stack=character;
  234.          string=decode_string(decode_stack+1,old_code);
  235.       }
  236.       else
  237.          string=decode_string(decode_stack,new_code);
  238.  
  239.       character = *string;              /* Output decoded string in reverse */
  240.       while (string >= decode_stack)
  241.          putc(*string--,output);
  242.  
  243.       if (next_code <= max_code) {      /* Add to string table if not full */
  244.          prefix_code[next_code]=old_code;
  245.          append_character[next_code++]=character;
  246.          if (next_code == max_code && num_bits < MAX_BITS) {
  247.             putchar('+');
  248.             max_code = MAXVAL(++num_bits);
  249.          }
  250.       }
  251.       old_code=new_code;
  252.    }
  253.    putchar('\n');
  254. }
  255. /* UNCHANGED from original
  256.  * Decode a string from the string table, storing it in a buffer.
  257.  * The buffer can then be output in reverse order by the expansion
  258.  * program.
  259.  */
  260. char *decode_string(unsigned char *buffer, unsigned int code)
  261. {
  262.    int i=0;
  263.  
  264.    while(code > 255 ) {
  265.       *buffer++ = append_character[code];
  266.       code=prefix_code[code];
  267.       if (i++ >= 4000 ) {
  268.          printf("Error during code expansion\n");
  269.          exit(1);
  270.       }
  271.    }
  272.    *buffer=code;
  273.    return(buffer);
  274. }
  275.  
  276. /* UNCHANGED from original
  277.  * Input a variable length code.
  278.  */
  279. unsigned input_code(FILE *input)
  280. {
  281.    unsigned int return_value;
  282.    static int input_bit_count=0;
  283.    static unsigned long input_bit_buffer=0L;
  284.  
  285.    while (input_bit_count <= 24 ) {
  286.      input_bit_buffer |= (unsigned long) getc(input) << (24 - input_bit_count);
  287.      input_bit_count += 8;
  288.    }
  289.    return_value=input_bit_buffer >> (32-num_bits);
  290.    input_bit_buffer <<= num_bits;
  291.    input_bit_count -= num_bits;
  292.    return(return_value);
  293. }
  294. /* MODIFIED Output a variable length code.
  295.  */
  296. output_code(FILE *output, unsigned int code)
  297. {
  298.    static int output_bit_count=0;
  299.    static unsigned long output_bit_buffer=0L;
  300.  
  301.    output_bit_buffer |= (unsigned long) code << (32 - num_bits - 
  302.                                                              output_bit_count);
  303.    output_bit_count += num_bits;
  304.    while (output_bit_count >= 8) {
  305.       putc(output_bit_buffer >> 24, output);
  306.       output_bit_buffer <<= 8;
  307.       output_bit_count -= 8;
  308.       bytes_out++;                    /* ADDED for compression monitoring */
  309.    }
  310. }
  311.  
  312.  
  313.  
  314.